Corelab Seminar
2020-2021
Chara Podimata
Contextual Search in the Presence of Irrational Agents
Abstract.
We study contextual search, a generalization of binary search in higher
dimensions, which captures settings such as feature-based dynamic
pricing. Standard game-theoretic formulations of this problem assume
that agents act in accordance with a specific behavioral model. In
practice, however, some agents may not prescribe to the dominant
behavioral model or may act in ways that are seemingly arbitrarily
irrational. Existing algorithms heavily depend on the behavioral model
being (approximately) accurate for all agents and have poor performance
in the presence of even a few such arbitrarily irrational agents.
We initiate the study of contextual search when some of the agents can
behave in ways inconsistent with the underlying behavioral model. In
particular, we provide two algorithms, one built on robustifying
multidimensional binary search methods and one on translating the
setting to a proxy setting appropriate for gradient descent. Our
techniques draw inspiration from learning theory, game theory,
high-dimensional geometry, and convex analysis.
This is joint work with Akshay Krishnamurthy, Thodoris Lykouris, and
Robert Schapire. The full version of the paper can be found here:
https://arxiv.org/pdf/2002.11650.pdf..